The present invention relates to a computer system, peripheral device, or component having a circuit for determining the maximum or minimum of a plurality of codes.
As an introduction to problems solved by the present invention, consider the conventional interrupt controller of a computer system. An interrupt controller is used with a processor or bus manager for determining which of several competing requests should be granted, based on a hierarchy of priority levels. For example, a conventional printer includes a processor for device control and data communications functions. This processor must service perhaps a dozen input/output circuits (called interrupt sources), each having an independent function (e.g. out of paper indicator, input data buffer full, scan line format complete, etc.). Although the processor could perform stored program instructions to determine in what order to service these numerous requests, these functions are more economically and efficiently performed by a dedicated circuit conventionally called an interrupt controller.
An interrupt controller generally receives an interrupt signal on a separate line from each interrupt source. Generally, when an interrupt signal is received, the interrupt controller signals the processor and the processor performs an interrupt acknowledge procedure to transfer control from the currently running task to the task that will service the interrupt. Transfer of processor execution control to a new address is conventionally accomplished via a table of addresses (called a vector table) indexed by an interrupt identifier. During the interrupt acknowledge procedure, the interrupt controller passes to the processor the interrupt identifier associated with the interrupt request signal.
In a system having numerous interrupt sources, various interrupt sources may require servicing ahead of other interrupt sources. And, the processor may require uninterrupted processing time. In such a system multiple interrupt requests may be asserted during a time when the processor is unavailable to service an interrupt. The interrupt controller, during such a time, maintains a request to the processor for interrupt servicing. When the processor becomes available and so indicates to the interrupt controller by beginning the interrupt acknowledgement procedure, the interrupt controller determines the currently pending highest priority interrupt and responds with an interrupt identifier for the appropriate interrupt source.
In a system where the program executed by the processor assigns interrupt identifiers to various input/output functions (either at system initialization or from time to time for sophisticated control functions), the value of an interrupt identifier may conveniently indicate by its binary magnitude the priority of the associated interrupt source over other interrupt sources. The interrupt identifier passed to the processor in an interrupt acknowledge procedure may be the interrupt identifier having the maximum binary value.
When a design having a large number of interrupt sources is to be expanded to service additional interrupt sources by a single processor in a conventional computer system design, the conventional interrupt controller design in its expanded form cannot avoid the undesirable side effects of increased circuit complexity and increased propagation delay. To be expandable, such a system design often propagates one or more carry signals from stage to stage in either an asynchronous or clocked manner. An expanded conventional circuit for accommodating additional interrupt sources has a considerably increased number of logic gates. Signal propagation through these additional gates also increases interrupt controller propagation delay. In other applications, the possibility of increasing propagation delay and/or circuit complexity cannot be accommodated within economic constraints of the planned product.
The problem of selecting the highest priority interrupt to service as discussed above with respect to input/output devices is similar in some respects to problems in other computer system components. For example, a multipurpose data communication bus shared by several devices is conventionally designed with a bus controller that permits exclusive use of the bus to a highest priority device. Priorities are designated conventionally by codes having a magnitude; the device associated with the code having the highest magnitude operates as the highest priority device. Generally any computer system resource (e.g. a processor, a bus, an input/output circuit, etc.) may be shared using a conventional circuit for arbitration. When presented with multiple pending requests to share the resource, such a circuit determines the highest priority request by determining the code having the highest magnitude. As another example, dedicated sorting logic for selecting data words in a sequence may also use a conventional circuit for selecting a xe2x80x9cnextxe2x80x9d data word based on determining the highest magnitude data word not previously selected. Excessive circuit complexity and excessive propagation delay in these and related applications raise severe constraints on the practical design and economic marketing of a wide range of computer systems and products controlled by digital logic circuits.
Markets continue to demand sophisticated computer systems and computer operated products. Because sophisticated products increasingly operate with a large number of input/output circuits, and because the control of input/output circuits by interrupt servicing is more efficient than control using polling techniques, there is a continuing need for an interrupt controller design that is expandable with less added complexity and that operates with less added propagation delay. Similarly, in applications for selecting a device or a data word according to a code (or the data word itself) having the highest magnitude, as discussed above, there is a continuing need for a circuit design that is expandable with less added complexity and that operates with less added propagation delay.
An arithmetic-logic circuit according to aspects of the present invention receives a plurality of input codes and determines an output code. Each code has a respective magnitude and is conveyed in parallel by a plurality of respective (input or output) code signals. The circuit includes several product term generators (one for each respective plurality of input code signals), a summary term generator, and a selection circuit. Each product term generator provides a respective plurality of product term signals. Each product term signal is indicative of an AND combination of respective input code signals. The summary term generator provides a plurality of summary term signals in parallel. Each summary term signal is indicative of an OR combination of a corresponding product term signal from each product term generator. The selection circuit provides the plurality of output code signals according to an extreme of the respective magnitudes of the input codes. At least one output code signal is indicative of an AND combination of a multiplicity of summary term signals of the plurality of summary term signals.
When such a circuit is used in an interrupt controller, as described above, expansion of the design to accommodate an additional interrupt source can be accomplished with little added complexity and no added propagation delay. For example, when the number of bits in the input code is sufficient to accommodate the additional interrupt source, then the additional input code is received by an additional product term generator that generates additional product terms and the summary term generator is modified to merely add an additional gate input for each additional product term. Propagation delay of the interrupt controller is substantially unaffected by these modifications.
When the number of input code bits must be incremented to accommodate an additional interrupt source, then the modifications described above are supplemented with the following modification. Each product generator is modified by adding a few gates and gate inputs for the additional input code bit. The summary term generator is modified by adding one gate. And, the selection circuit is modified to add a multiplexer. Propagation delay is affected only by the addition of the multiplexer. The increase in circuit complexity is quite modest compared to corresponding increased complexity of conventional circuit designs.
A printer, according to various embodiments of the present invention includes a print engine, and a printer controller. The print engine prints data on media and in operation provides a plurality of pending interrupt request signals. The printer controller includes a processor for providing data to the print engine in accordance with an output code received in parallel by a plurality of output code signals and an interrupt controller. The interrupt controller includes both a register and a product term generator for each pending interrupt request signal, and includes a summary term generator and selection circuit. The register stores an input code and provides a respective multiplicity of input code signals in parallel to convey the respective input code. Each respective product term generator is coupled to the respective register and provides a respective plurality of product term signals. Each product term signal is indicative of an AND combination of respective input code signals. The summary term generator provides a plurality of summary term signals in parallel, each summary term signal indicative of an OR combination of a corresponding product term signal from each product term generator. The selection circuit provides the output code signals to convey an output code that is an extreme (e.g. a maximum or minimum) of the input codes associated with the pending interrupt request signals.
A computer system, according to various embodiments of the present invention includes a shared resource, an arbitration circuit, and a plurality of devices that compete to cooperate with the shared resource. Each device provides a respective device signal. The arbitration circuit includes a respective input code register that stores an input code having a magnitude associated with a device of the plurality of devices. Each register provides, in response to the corresponding device signal, a respective plurality of input code signals in accordance with the respective stored input code. The arithmetic-logic circuit includes product term generators, a summary term generator, and a selection circuit as discussed above. The selection circuit provides the plurality of output code signals according to an extreme of the respective magnitudes of the input codes. At least one output code signal is indicative of an AND combination of a multiplicity of summary term signals of the plurality of summary term signals. The resource includes a controller that receives the output code signals and controls cooperation of the resource with the device associated with the input code corresponding to the extreme of the respective magnitudes of the input codes.
A method according to various embodiments of the present invention determines an output code having a magnitude corresponding to an extreme magnitude of a plurality of input codes, each input code having a magnitude. Each input code (and the output code) is conveyed by a respective plurality of input (or output) code signals. The method, in one embodiment includes the steps of (a) storing the plurality of input codes in a memory; (b) providing a multiplicity of input codes from the memory to an arithmetic-logic circuit of the type discussed above; and (c) obtaining the output code from the arithmetic-logic circuit by receiving the plurality of output code signals.
The beneficial results discussed above with reference to an interrupt controller including low circuit complexity, low propagation delay, less added circuit complexity, and less added propagation delay, may be obtained in a wide variety of applications according to the present invention, for example, a bus controller, a resource sharing arbitration circuit, and a sorting circuit. In such applications overall system performance improvements and greater system responsiveness may be evident to the system user. Use of systems and methods of the present invention may result in economic feasibility of a wide range of computer systems, computer operated products, and specialized logic circuits heretofore unavailable to the market.